package Offer1218;

import java.util.HashMap;

/**
 * 最长定差子序列
 * 给你一个整数数组arr和一个整数difference，请你找出并返回 arr中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。
 * 子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。
 * @author 23737
 * @time 2021.11.05
 */
public class Test {
    public static void main(String[] args) {
        System.out.println(new Solution().longestSubsequence(new int[]{1, 5, 7, 8, 5, 3, 4, 2, 1}, -2));
    }
}

/**
 * dp动归解题
 * 动归方程：fun(arr[i]) = fun(arr[i]-difference)-1
 */
class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int max = 0;
        for (int i = 0; i<arr.length; i++) {
            map.put(arr[i], map.getOrDefault(arr[i]-difference,0)+1);
            max = Math.max(map.get(arr[i]),max);
        }
        return max;
    }
}
